/**
 * 剑指 Offer 47. 礼物的最大价值
 * https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
 */

/**
 * @param {number[][]} grid
 * @return {number}
 */
function maxValue(grid) {
  const { length: m } = grid;
  const { length: n } = grid[0];
  const dp = new Array(m);
  for (let i = 0; i < m; i += 1) {
    dp[i] = new Array(n);
  }
  [[dp[0][0]]] = grid;
  for (let i = 1; i < m; i += 1) {
    dp[i][0] = grid[i][0] + dp[i - 1][0];
  }
  for (let j = 1; j < n; j += 1) {
    dp[0][j] = grid[0][j] + dp[0][j - 1];
  }
  for (let i = 1; i < m; i += 1) {
    for (let j = 1; j < n; j += 1) {
      dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
  }
  return dp[m - 1][n - 1];
}

console.log(maxValue([
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1],
]) === 12);
